#define _CRT_SECURE_NO_WARNINGS
//void reverse(int* nums, int left, int right)
//{
//    while (left < right)
//    {
//        int tmp = nums[left];
//        nums[left] = nums[right];
//        nums[right] = tmp;
//        left++;
//        right--;
//    }
//}
//void rotate(int* nums, int numsSize, int k) {
//    k = k % numsSize;
//    reverse(nums, 0, numsSize - k - 1);
//    reverse(nums, numsSize - k, numsSize - 1);
//    reverse(nums, 0, numsSize - 1);
//}
//
//int missingNumber(int* nums, int numsSize) {
//    int ret = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        ret ^= nums[i];
//        ret ^= i;
//    }
//    ret ^= numsSize;
//    if (ret == 0)
//        return 0;
//    return ret;
//}
//
//
//int removeDuplicates(int* nums, int numsSize) {
//    if (numsSize == 0)
//        return 0;
//    int fast = 1, slow = 1;
//    while (fast < numsSize)
//    {
//        if (nums[fast] != nums[fast - 1])
//        {
//            if (fast != slow)
//                nums[slow] = nums[fast];
//            slow++;
//        }
//        fast++;
//    }
//    return slow;
//}
#include <stdio.h>
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* newhead = reverse(head);
    struct ListNode* pcur = newhead;
    while (--k)
    {
        pcur = pcur->next;
    }
    return pcur->val;
}
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, * n2, * n3;
    if (head == NULL)
        return head;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}
struct ListNode* FindMid(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
bool isPalindrome(struct ListNode* head) {
    struct ListNode* mid = FindMid(head);
    struct ListNode* newhead = reverseList(mid);
    struct ListNode* pcur1 = head, * pcur2 = newhead;
    while (pcur1 && pcur2)
    {
        if (pcur1->val != pcur2->val)
            return false;
        pcur1 = pcur1->next;
        pcur2 = pcur2->next;
    }
    return true;
}